package com.yulongtian.algorithms.binarysearch01;

/**
 * https://leetcode.cn/problems/kth-missing-positive-number/
 *
 * @author yulongTian
 * @create 2023-02-01 11:08
 */
public class Test04 {
    public static void main(String[] args) {

    }

    /**
     * 第一眼看过去人都蒙了, 后来想了一下, 假设这个数组是空的,
     * 那么给的k就是所缺的数, 如果数组不空, 但是所有的数都大于k,
     * 那么这个数组缺失了1~k, k还是所缺的数. 数组中所有的数都小于k ,
     * 则判断有n个数, k+n是所缺数 数组中有小于k的有大于k的,
     * 比如{1,2,6,7}, 取k=4,
     * 则在该判断中, 经过1和2的后, k=6, 此时6和7也满足了条件,
     * 于是k = 8居然也行了... k在每一个小于它的数那里获得+1,
     * 并从小到大依次挑战, 直到全部挑战完毕...
     * 这是哪个大佬想出来的啊???
     *
     * @param arr
     * @param k
     * @return
     */
    public int findKthPositive(int[] arr, int k) {
        for (int n : arr) {
            if (n <= k) {
                k++;
            } else break;
        }
        return k;
    }

}
